package com.niuke;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

/**
 * 21. 最大值
 * 只找到最大数字 https://zhuanlan.zhihu.com/p/642208359
 */
public class NiukeMoni21nan {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        char[] c = input.toCharArray();

        Map<Character, Integer> unused = new HashMap<>();
        Map<Character, Integer> reserve = new HashMap<>();

        for (int i = 0; i < c.length; i++) {
            unused.put(c[i], unused.getOrDefault(c[i], 0) + 1);
        }

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < c.length; i++) {
            if (reserve.getOrDefault(c[i], 0) == 2) {
                continue;
            }

            /**
             * 判断当前的 char 比之前栈顶的大，并且栈顶的这个数后面还有很多可以使用，
             * 就把栈顶这个数抛弃，让当前这个较大的数顶替到前面，这样才能保证结果相对较大。
             */
            while (stack.size() > 0) {
                char top = stack.peek();
                if (top < c[i] && unused.getOrDefault(top, 0) + reserve.getOrDefault(top, 0) > 2) {
                    stack.pop();
                    reserve.put(top, reserve.getOrDefault(top, 0) - 1);
                } else {
                    break;
                }
            }

            stack.push(c[i]);
            unused.put(c[i], unused.getOrDefault(c[i], 0) - 1);
            reserve.put(c[i], reserve.getOrDefault(c[i], 0) + 1);
        }

        System.out.println(Arrays.toString(stack.toArray()));

    }

}
